#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
double LRU(int x, vector<int>&a) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;//堆，弹出最近最久未使用的块
    int sz = 0, cnt = 0, n = a.size() - 1;
    vector<int>vis(n + 1, 0);
    vector<int>b(n + 1, 0);//懒惰删除
    for (int i = 1; i <= n; ++i) {
        if (vis[a[i]]) {
            ++cnt;
            pq.push({i, a[i]});
            b[a[i]] = i;
        } else if(sz < x) {
            ++sz;
            pq.push({i, a[i]});
            b[a[i]] = i;
            vis[a[i]] = 1;
        } else {
            auto p = pq.top();
            while (!vis[p.second] || b[p.second] != p.first) {
                pq.pop();
                p = pq.top();
            }
            vis[pq.top().second] = 0;
            pq.pop();
            pq.push({i, a[i]});
            b[a[i]] = i;
            vis[a[i]] = 1;
        }
    }
    return (double)cnt / n;
}

double FIFO(int x, vector<int>&a) {
    queue<int>q;
    int cnt = 0, n = a.size();
    vector<int>in(1024, 0);
    for (int i = 0; i < a.size(); ++i) {
        if(!in[a[i]]) {
            if (q.size() < x) {
                q.push(a[i]);
                in[a[i]] = 1;
            } else {
                in[q.front()] = 0;
                q.pop();
                q.push(a[i]);
                in[a[i]] = 1;
            }
        } else {
            ++cnt;
        }
    }
    return (double)cnt / a.size();
}
void find_belady() {
    int n = 20;
    vector<int>p(n, 0);
    while (1) {
        for (int i = 0; i < n; ++i) {
            p[i] = rand() % 10;
        }
        for (int k = 1; k <= 8; ++k) {
            if (FIFO(k, p) > FIFO(k + 1, p)) {
                printf("%d:", k);
                for (int x : p) {
                    printf(" %d", x);
                }
                puts("");
                return;
            }
        }
    }
}
/**
页框大小为4和5的时候如下数据会出现belady效应
3, 2, 5, 1, 4, 0, 0, 9, 2, 1, 4, 5, 2, 3, 4, 1, 9, 5, 6, 5
**/
int main() {
    //vector<int>p{0, 1, 2, 3, 0, 1 ,4, 0, 1 ,2 ,3 ,4};
    //printf("%f %f\n", FIFO(3, p), FIFO(4, p));
    vector<int>p{3, 2, 5, 1, 4, 0, 0, 9, 2, 1, 4, 5, 2, 3, 4, 1, 9, 5, 6, 5};
    printf("%f %f\n", FIFO(4, p), FIFO(5, p));
    return 0;
}

